1246. Наименьшая сумма НОК

НОК (наименьшее общее кратное) множества целых чисел определяется как наименьшее число, которое делится на каждое число из этого множества. Интересно заметить, что любое натуральное число может быть выражено как НОК некоторого множества натуральных чисел. Например, 12 можно представить как НОК чисел 1, 12, или 12, 12, или 3, 4, или 4, 6, или 1, 2, 3, 4 и так далее.

В задаче задано натуральное число n. Необходимо найти множество, содержащее как минимум два числа, НОК чисел которого равно n. Поскольку таких множеств может быть бесконечное количество, Вам следует найти такое, для которого сумма его элементов минимальна. Мы будем предельно счастливы, если Вы также напечатаете и указанную сумму. Например, для n = 12 необходимо вывести 4 + 3 = 7, так как НОК чисел 4 и 3 равно 12, а 7 - наименьшее возможное значение суммы чисел множества.

Вход. Состоят из не более чем 100 тестов. Каждый тест состоит из натурального числа n (1 ≤ n ≤ 2³¹ – 1). Последний тест содержит n = 0 и не обрабатывается. Входные данные содержат не более 100 тестов.

Выход. Для каждого теста в отдельной строке вывести его номер в формате "Case #: " (# - номер теста). После чего следует вывести наименьшее значение суммы элементов искомого множества.

Пример входа	Пример выхода
12 10 5 0	Case 1: 7 Case 2: 7 Case 3: 6

РЕШЕНИЕ

НОК, разложение на множители

Анализ алгоритма

Обозначим через f(n) наименьшее значение суммы элементов искомого множества.

Если n = 1, то искомым множеством будет {1, 1} и f(n) = 2.

Если n простое, то искомым множеством будет {n, 1} и f(n) = n + 1.

Если n = p^a (p простое), то искомым множеством будет { p^a, 1} и f(n) = p^a + 1.

Если n = (p_i простое), то искомым будет множество и f(n) = .

Реализация алгоритма

Функция factor раскладывает число n на множители и возвращает значение f(n). В переменной с подсчитываем количество простых делителей числа n.

long long factor(long long n)

{

long long i, temp, c = 0, res = 0, nn = n;

if (n == 1) return 2;

for(i = 2; i <= sqrt(1.0*n); i++)

{

if(n % i == 0)

{

temp = 1;

while(n % i == 0)

{

temp *= i;

n /= i;

}

res += temp; c++;

}

}

if (n > 1) res += n, c++;

Если n = nn, то n простое число. В этом случае f(n) = n + 1.

if (n == nn) res++;

Если n не простое число, но количество простых делителей числа n равно единице (c = 1), то n = p^a для некоторого а. Тогда f(n) = p^a + 1.

else if (c == 1) res++;

return res;

}

Основная часть программы.

while(scanf("%lld",&n),n)

{

res = factor(n);

printf("Case %lld: %lld\n",cs++,res);

}